1. Field of the Invention
The present invention relates generally to a multi-stage channel interleaver/deinterleaver for a radio communication system, and in particular, to an address generating device for use in a multi-stage channel interleaver/deinterleaver.
2. Description of the Related Art
Generally, a radio communication system in which there exists a channel fading effect, performs channel interleaving and deinterleaving for mitigating the channel fading effect in order to ensure stable communication of digital source data to be transmitted by wire or wirelessly. For example, an IMT-2000 (International Mobile Telecommunication-2000) radio communication system, i.e., UMTS (Universal Mobile Telecommunication System) or CDMA-2000 (Code Division Multiple Access-2000) radio communication system, includes channel interleaver and deinterleaver for mitigating the channel fading effect.
With regard to a fundamental radio frame structure of the 3GPP (3rd Generation Partnership Project), the radio frame has a length of 10 ms and is comprised of 16 time slots. Therefore, standardization for each part of the system tends to be carried out based on the above frame structure. A fixed size multi-stage interleaver (FS-MIL) which is determined as a working assumption of a 2nd interleaver is a 2-dimensional interleaver, in which the number of columns is fixed to 32. The MIL interleaver is designed to support a frame structure comprised of 16 time slots, and transmits data corresponding to 2 columns per time slot. Since the 1st interleaver and the 2nd interleaver both have a hardware structure supporting the number of columns which is a power of 2, it is possible to support both the 1st interleaver and the 2nd interleaver using one hardware module, thus reducing the hardware complexity.
In the meantime, harmonization of the CDMA-2000 system, which is North-American IMT-2000 system, and the European UMTS system is in progress. However, the CDMA-2000 system uses a radio frame structure comprised of 16 time slots per frame, and the UMTS uses a radio frame structure comprised of 15 time slots per frame. Therefore, it is not possible to use the existing CDMA-2000 channel interleaver, designed based on the 16 time slots per frame, for a UMTS channel interleaver. Thus, it is necessary to design the UMTS channel interleaver based on 15 time slots per frame.
FIG. 1 illustrates a fundamental MIL interleaving technique performed in the general 2nd interleaver. A 10 ms input sequence is interleaved in the manner shown in FIG. 1. When the length of an input sequence is Lxe2x89xa6Fxc3x97B, the input sequence is stored in a 2-dimensional memory having a size of Fxc3x97B, where F is the number of columns of the interleaver and B is the number of rows of the interleaver. Further, B is a minimum integer which satisfies Lxe2x89xa6Fxc3x97B for fixed F. At this point, the data is sequentially stored in the interleaver one row at a time. An other words, the data is stored in the first row and fill the first row before the data is stored in the second row and so on. Thus, the data is stored one row at a time starting from the top row with the data fills the bottom row. The sequentially stored input sequence are sequentially output as data corresponding to the respective rows of a given column in the order of the inter-column permutation pattern shown in Table 1 below. Table 1 shows a permutation pattern for F=32.
FIG. 2 illustrates an address generating device for the MIL interleaver according to the prior art. In this address generating device, the number of columns is 32 which is a power of 2. Although a description of the address generating device will be made for the case where it is applied to the channel interleaver, it will be understood by those skilled in the art that the address generating device may be applied to the channel deinterleaver.
Referring to FIG. 2, the address generating device includes a row counter 210, a column counter 230, a mapper 240, a 5-bit shifter 220, and an adder 250, which are the elements for generating an address to be used for the 2nd channel interleaver. The row counter 210 and the column counter 230 count rows and columns of an interleaving memory (not shown), respectively. In the memory, the input data is sequentially stored in the order of row and column. The mapper 240 maps the columns counted by the column counter 230 to permuted columns. For example, the mapper 240 outputs the columns counted by the column counter 230 as permuted columns according to the inter-column permutation pattern shown in Table 1. The bit shifter 220 bit-shifts the value counted by the row counter 210. The adder 250 forms a new address by using the output of the bit shifter 220 as the most significant bits(MSB) of the new address and by using the output of the mapper 240 as the least significant bits(LSB) of the new address. Such an address is used to output the data which was sequentially stored in the memory in the order of row and column, as 2-dimensional interleaved data.
In the meantime, the conventional address generating device for the MIL interleaver includes the bit shifter 220. Such a bit shifter 220 is implemented by a 5-bit shifter, when the number of the columns is 32 which is a power of 2.
As described above, when the number of the columns is 32 which is a power of 2, a bit shift operation is performed by the 5-bit shifter 220 in order to obtain an address from the row counter 210. Here, the bit shifter 220 has a low hardware complexity.
However, if the number of time slots per frame is changed from 16 to 15, the number of the columns will also be changed, and there is a high probability that the new number of columns will not be a power of 2. For example, if it is assumed that the number of columns per time slot is 2 and the total number of the columns is 30, 30 multipliers are required and the hardware size of the multipliers will increase about twice the hardware size for the MIL 2nd interleaver. When the number of columns of the MIL interleaver is not a power of 2 as stated above, it is not possible to use the bit shift operation as in the MIL 1st interleaver for which the number of columns is 1, 2, 4 and 8. Therefore, there are required the multipliers, the number of which corresponds to the number of columns. In this case, the total hardware complexity of the interleaver increases about two times.
It is, therefore, an object of the present invention to provide an address generating device for implementing a MIL interleaver with the decreased hardware complexity.
It is another object of the present invention to provide an address generating device for performing an interleaving operation without an increase in the hardware complexity of an interleaver, even when the number of the columns of the MIL interleaver is not a power of 2.
It is further another object of the present invention to provide a device for generating an address for MIL 1st and 2nd interleavers using a single module.
To achieve the above and other objects, There is provided an address generating device for reading data from an interleaver memory having B rows by F columns, where the data from the memory are interleaved one column at a time by following predetermined column permutation rule. In addition the number of columns in the interleaver memory, F is not equal to an integer power of 2, i.e. Fxe2x89xa02k where k is a positive integer. An row counter responsive to B clock pulses, output offset values from 0 to (Bxe2x88x921)xc3x97F in increments of F, each offset value outputted with successive clock pulses, and generates a carry signal when the B clock pulses are completed. A column counter increases a count value in increments of one in response to the carry signal. A mapper permutates a signal sequence output from the column counter. An adder adds the permuted signal sequence output from the mapper to the signal output from the row counter to generate the addresses.